package com.cxq.sort;

import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {5, 6, 2, 1, 4, 7, 8, 9, 3};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    private static void quickSort(int[] arr, int start, int end) {
        if (start < end) {
            //标准数
            int stard = arr[start];
            //定义左边的指针
            int low = start;
            //定义右边的指针
            int high = end;
            while (low < high) {
                //首先判断右边的数字是否大于标准数
                //如果是的话只需要把右边的指针向前移动一位
                while (low < high && stard < arr[high]) {
                    high--;
                }
                //如果不是就需要跳出循环，把右边的数字赋给左边的数字
                arr[low] = arr[high];

                //再判断左边的数字是否小于标准数
                //如果是的话只需要把左边的指针向前移动一位
                while (low < high && stard > arr[low]) {
                    low++;
                }
                //如果不是就会跳出循环，把左边的数字赋值给右边的数字
                arr[high] = arr[low];
            }
            //再把标准数赋值给现在low和high重合位置的值
            arr[low] = stard;

            // 使用递归的思想
            quickSort(arr, 0, low);
            quickSort(arr, low + 1, end);
        }
    }
}